/*
 * bwt.cpp
 */
/*
 // Comparar dos rotaciones del bloque que comienzan en las
 // posiciones apuntadas por los punteros p1 y p2.
 // Si rotacion1 > rotacion2, devuelve  1
 // Si rotacion1 < rotacion2, devuelve -1
 // Si rotacion1 == rotacion2, devuelve  0
 int comparar(int *p1, int *p2) {
 int i = *p1;
 int j = *p2;
 int aux = (i == 0) ? longitud : i;

 do {
 if (bloque[i] != bloque[j]) {
 if (bloque[i] < bloque[j]) {
 return -1;
 } else {
 return 1;
 }
 }
 if (++i == longitud) i = 0;
 if (++j == longitud) j = 0;
 } while (i != aux);

 return 0;
 }

 // Transformar un bloque de caracteres usando BWT.
 // Recibe un bloque de caracteres desde la entrada.
 // Supone una matriz con todas las rotaciones del bloque.
 // Ordena esa matriz, y devuelve la ultima columna y la
 // posicion (fila) del bloque original en la matriz ordenada.
 void bwt_codificar(int bloque[], int longitud) {
 int iguales = 1;
 int indice[CANTIDAD];
 int ultima[CANTIDAD + 4];
 int fila = 0;
 int i;

 // Si todos los caracteres del bloque son iguales, no es
 // necesaria la transformacion BWT (optimizacion a raiz
 // de un caso planteado en el Corpus Canterbury: aaa.txt)
 for (i = 1; i < longitud; i++) {
 if (bloque[0] != bloque[i]) {
 iguales = 0;
 break;
 }
 }

 // en la gran mayoria de los casos se hace la transformacion
 if (!iguales) {
 // inicializa un indice de filas para la matriz
 for (i = 0; i < longitud; i++) {
 indice[i] = i;
 }

 // Ordena el indice, segun el orden de las rotaciones del bloque,
 // usando la funcion qsort de la biblioteca standard de C, que
 // recibe una funcion comparar como parametro.
 qsort(indice, longitud, sizeof(int), (int (*)(const void*, const void*))comparar);

 // Obtiene la ultima columna de la matriz ordenada y
 // la fila correspondiente al bloque original.
 for(		i = 0; i < longitud; i++)
 {
 if (indice[i] != 0) {
 ultima[i] = bloque[indice[i]-1];
 } else {
 ultima[i] = bloque[longitud-1];
 fila = i;
 }
 }

 // Descompone fila en dos partes y las pone al final del array,
 // para que sean codificadas en las etapas siguientes
 ultima[longitud] = (0xFF & fila);
 ultima[longitud + 1] = (0xFF & (fila >> 8));
 ultima[longitud + 2] = (0xFF & (fila >> 16));
 ultima[longitud + 3] = (0xFF & (fila >> 24));

 // devuelve el resultado en el bloque
 memcpy(bloque, ultima, sizeof(ultima));
 }
 }

 // Transformar inversamente un bloque de caracteres usando BWT.
 // Recibe la ultima columna de la matriz ordenada y la
 // ubicacion (fila) del bloque original en esa matriz.
 // Construye un indice de la primera columna de la matriz ordenada.
 // Con ese indice construye una referencia de las posiciones
 // de la primera columna en la ultima columna.
 // Con la referencia y la fila recupera el bloque original.
 void bwt_decodificar(int bloque[], int longitud)
 {
 int fila = 0;
 int ultima[CANTIDAD];
 int indice[RANGO];
 int referencia[CANTIDAD];

 int suma = 0;
 int frecuencia = 0;
 int caracter = 0;
 int i, j;

 // Recupera el dato de la fila.
 fila = (bloque[longitud + 3] << 24 | bloque[longitud + 2] << 16
 | bloque[longitud + 1] << 8 | bloque[longitud]);

 // copia el bloque en el array u ltima
 memcpy(ultima, bloque, sizeof(ultima));

 // inicializa un indice con 256 posiciones
 for(i = 0; i < RANGO; i++)
 {
 indice[i] = 0;
 }

 // Almacena en el indice la frecuencia de los caracteres
 // presentes en la ultima columna
 for(i = 0; i < longitud; i++)
 {
 caracter = ultima[i];
 indice[caracter]++;
 }

 // Sabiendo que la primera columna de la matriz estaba ordenada,
 // obtiene un "indice compacto" de la primera columna haciendo
 // una suma acumulativa de frecuencias en el indice.
 for(i = 0; i < RANGO; i++)
 {
 frecuencia = indice[i];
 indice[i] = suma;
 suma += frecuencia;
 }

 // Usando el "indice compacto" obtiene las posiciones de los
 // elementos de la primera columna en la ultima columna,
 // y las almacena en el array referencia
 for(i = 0; i < longitud; i++)
 {
 caracter = ultima[i]; // caracter en ultima
 j = indice[caracter]; // frec. acumulada = posicion en primera
 referencia[j] = i;    // referencia cruzada
 indice[caracter]++;   // incrementa indice = avanza en primera
 }

 // Usando la referencia y la fila, recupera el bloque original
 j = fila;
 for(i = 0; i < longitud; i++)
 {
 j = referencia[j];
 bloque[i] = ultima[j];
 }
 }
 */
